// Copyright (c) 2002-2009 "Neo Technology,"
//     Network Engine for Objects in Lund AB [http://neotechnology.com]
// *
// This file is part of Neo4j.
// 
// Neo4j is free software: you can redistribute it and/or modify
// it under the terms of the GNU Affero General Public License as
// published by the Free Software Foundation, either version 3 of the
// License, or (at your option) any later version.
// 
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU Affero General Public License for more details.
// 
// You should have received a copy of the GNU Affero General Public License
// along with this program. If not, see <http://www.gnu.org/licenses/>.
#region Using Directives

using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using org.neo4j.graphdb;
using org.neo4j.kernel.impl.util;

using Direction = org.neo4j.graphdb.Direction;
using Node = org.neo4j.graphdb.Node;
using NotFoundException = org.neo4j.graphdb.NotFoundException;
using Relationship = org.neo4j.graphdb.Relationship;
using RelationshipType = org.neo4j.graphdb.RelationshipType;
using ReturnableEvaluator = org.neo4j.graphdb.ReturnableEvaluator;
using StopEvaluator = org.neo4j.graphdb.StopEvaluator;
using TraversalPosition = org.neo4j.graphdb.TraversalPosition;
using Traverser = org.neo4j.graphdb.Traverser;

#endregion
namespace org.neo4j.kernel.impl.traversal
{
    /// <summary> 
    ///  This class provides a skeletal implementation of the <seealso cref="Traverser"/>
    /// interface to minimize the effort required to implement the
    /// <seealso cref="BreadthFirstTraverser"/> and <seealso cref="DepthFirstTraverser"/>. This is a
    /// package private class used only for implementation-reuse purposes. Any
    /// documentation interesting to a client programmer should reside in
    /// <seealso cref="Traverser"/>.
    /// The AbstractTraverser contains the logic and functionality that is common to
    /// both traverser subtypes. In reality, this means ALL functionality except for
    /// the data structure used to store the traverser list (captured via the four
    /// abstract operations <seealso cref="InitializeList"/>,
    /// <seealso cref="AddPositionToList"/>,
    /// <seealso cref="GetNextPositionFromList"/> and
    /// <seealso cref="ListIsEmpty"/>) and whether children are processed in
    /// natural- or reverse order (captured via the abstract operation
    /// <seealso cref="TraverserChildrenInNaturalOrder" />).
    /// In order to minimize overhead, the AbstractTraverser caches the result of
    /// <seealso cref="HasNext"/> so that the subsequent implementation of <seealso cref="Next"/> or
    /// <seealso cref="NextNode"/> won't have to redo the traversal.
    ///  </summary>
    /// <seealso cref="Traverser"> </seealso>
    /// <seealso cref= "BreadthFirstTraverser"></seealso>
    /// <seealso cref=" DepthFirstTraverser"> </seealso>
    /// 
    internal abstract class AbstractTraverser : Traverser, IEnumerator<Node>
    {
        #region Private Variables

        /// <summary>
        /// 
        /// </summary>
        private RelationshipType[] traversableRels = null;
        /// <summary>
        /// 
        /// </summary>
        private Direction[] traversableDirs = null;
        /// <summary>
        /// 
        /// </summary>
        private RelationshipType[] preservingRels = null;
        /// <summary>
        /// 
        /// </summary>
        private Direction[] preservingDirs = null;
        /// <summary>
        /// 
        /// </summary>
        private StopEvaluator stopEvaluator = null;
        /// <summary>
        /// 
        /// </summary>
        private ReturnableEvaluator returnableEvaluator = null;
        /// <summary>
        /// 
        /// </summary>
        private HashSet<Node> visitedNodes = new HashSet<Node>();
        /// <summary>
        /// 
        /// </summary>
        private Node cachedNode = null;
        /// <summary>
        /// 
        /// </summary>
        private int returnedNodesCount = 0;
        /// <summary>
        /// 
        /// </summary>
        private TraversalPositionImpl traversalPosition = null;

        #endregion

        #region Class Constructors

        /// <summary>
        /// Creates an AbstractTraverser subclass, for information about the
        /// arguments please see the documentation of <seealso cref="InternalTraverserFactory"/>.
        /// </summary>
        /// <param name="startNode"></param>
        /// <param name="traversableRels"></param>
        /// <param name="traversableDirs"></param>
        /// <param name="preservingRels"></param>
        /// <param name="preservingDirs"></param>
        /// <param name="stopEvaluator"></param>
        /// <param name="returnableEvaluator"></param>
        /// <param name="randomEvaluator"></param>
        internal AbstractTraverser(Node startNode, RelationshipType[] traversableRels, Direction[] traversableDirs, RelationshipType[] preservingRels, Direction[] preservingDirs, StopEvaluator stopEvaluator, ReturnableEvaluator returnableEvaluator, RandomEvaluator randomEvaluator)
        {
            // Sanity check
            if (startNode == null || traversableRels == null || stopEvaluator == null || returnableEvaluator == null)
            {
                string s = "startNode = " + startNode + ", traversableRels = " + ConvertStringArrayToStringJoin(traversableRels) + ", stopEvaluator = " + stopEvaluator + ", returnableEvaluator = " + returnableEvaluator;
                throw new IllegalArgumentException("null argument(s): " + s);
            }

            // Assign attributes
            this.traversableRels = traversableRels;
            this.traversableDirs = traversableDirs;
            this.preservingRels = preservingRels;
            this.preservingDirs = preservingDirs;
            this.stopEvaluator = stopEvaluator;
            this.returnableEvaluator = returnableEvaluator;

            // Initialize the (subclass-specific) traverser list
            this.InitializeList();

            // Add the first position to the list
            TraversalPositionImpl firstPos = this.createPosition(startNode, null, null, 0);
            this.AddPositionToList(firstPos);
        }

        #endregion

        #region Implementations

        #region Private Implementations

        /// <summary>
        /// 
        /// </summary>
        /// <param name="array"></param>
        /// <returns></returns>
        private string ConvertStringArrayToStringJoin(IEnumerable<RelationshipType> array)
        {
            StringBuilder builder = new StringBuilder();
            foreach (RelationshipType value in array)
            {
                builder.Append(value.Name());
                builder.Append('.');
            }
            return builder.ToString();
        }


        /// <summary>
        /// Traverses to the next node and returns it, or null if there are
        /// no more nodes in this traversal
        /// </summary>
        /// <returns></returns>
        private Node TraverseToNextNode()
        {
            Node nodeToReturn = null;

            while (!this.ListIsEmpty() && nodeToReturn == null)
            {
                // Get next node from the list
                TraversalPositionImpl currentPos = this.GetNextPositionFromList();
                traversalPosition = currentPos;
                Node currentNode = currentPos.CurrentNode();

                // Make sure we haven't visited this node before: add() returns
                // true if the set doesn't contain the node -- which means that
                // we're fine.
                if (visitedNodes.Add(currentNode))
                {
                    // Update position with however many nodes we've returned
                    // from the traversal up until now, this may be used to
                    // determine whether we should stop and/or return currentPos
                    currentPos.SetReturnedNodesCount(this.returnedNodesCount);

                    // If we're not stopping, then add related nodes to the list
                    // or current position not valid (last trav rel deleted)
                    if (!this.stopEvaluator.IsStopNode(currentPos))
                    {
                        // Add the nodes at the end of all traversable- and
                        // preserving relationships
                        try
                        {
                            this.AddEndNodesToList(currentPos, this.traversableRels, this.traversableDirs);
                            this.AddEndNodesToList(currentPos, this.preservingRels, this.preservingDirs);
                        }
                        catch (NotFoundException e)
                        {
                            // currentNode deleted in other tx
                            // try next position from list
                            continue;
                        }
                    }

                    // Check if we should return currentPos
                    if (this.returnableEvaluator.IsReturnableNode(currentPos))
                    {
                        this.returnedNodesCount++;
                        nodeToReturn = currentPos.CurrentNode();
                    }
                }
            }

            return nodeToReturn;
        }
        /// <summary>
        /// Adds the nodes at the end or start (depending on 'dirs') of all
        /// relationships of a type in 'relTypes' that are attached to the
        /// node in 'currentPos' to the list
        /// </summary>
        /// <param name="currentPos"></param>
        /// <param name="relTypes"></param>
        /// <param name="dirs"></param>
        private void AddEndNodesToList(TraversalPositionImpl currentPos, RelationshipType[] relTypes, Direction[] dirs)
        {
            if (relTypes == null)
            {
                return;
            }

            // Get the node and compute new depth
            Node currentNode = currentPos.CurrentNode();
            int newDepth = currentPos.Depth() + 1;

            // For all relationship types...
            for (int i = 0; i < relTypes.Length; i++)
            {
                // ... get all rels of that type and direction from currentNode
                IEnumerable<Relationship> rels = null;
                try
                {
                    if (dirs == null || dirs[i] == Direction.BOTH || dirs[i] == null)
                    {
                        rels = currentNode.GetRelationships(relTypes[i]);
                    }
                    else
                    {
                        rels = currentNode.GetRelationships(relTypes[i], dirs[i]);
                    }
                }
                catch (NotFoundException e)
                {
                    // node deleted in other tx
                }

                // The order we process relationships is really irrelevant, but
                // as long as we have a non-deterministic ordering in
                // currentNode.getRelationship(), we'll have to resort to ugly
                // hacks like this to be able to return the branches in the
                // the order that people generally expect.

                if (rels != null)
                {
                    foreach (Relationship rel in rels)
                    {
                        this.ProcessRel(currentNode, rel, newDepth);
                    }
                }
            }
        }
        /// <summary>
        /// 
        /// </summary>
        /// <param name="currentNode"></param>
        /// <param name="rel"></param>
        /// <param name="newDepth"></param>
        private void ProcessRel(Node currentNode, Relationship rel, int newDepth)
        {
            Node endNode = rel.getOtherNode(currentNode);
            TraversalPositionImpl newPos = this.createPosition(endNode, currentNode, rel, newDepth);
            this.AddPositionToList(newPos);
        }
        /// <summary>
        ///  Creates a traversal position populated with the specified data
        /// </summary>
        /// <param name="currentNode"></param>
        /// <param name="previousNode"></param>
        /// <param name="lastRelTraversed"></param>
        /// <param name="currentDepth"></param>
        /// <returns></returns>
        private TraversalPositionImpl createPosition(Node currentNode, Node previousNode, Relationship lastRelTraversed, int currentDepth)
        {
            return new TraversalPositionImpl(currentNode, previousNode, lastRelTraversed, currentDepth);
        }

        #endregion

        #region Internal Implementations

        /// <summary> 
        /// Instantiates the underlying container used to store future traversal
        /// positions. This operation is required to overcome, ehum, "limitations" in
        /// the way java resolves constructors and field initialization in complex
        /// inheritance hierarchies.
        ///  </summary>
        internal abstract void InitializeList();
        /// <summary>
        /// Adds <CODE>position</CODE> to the end of the list.
        /// </summary>
        /// <param name="position"></param>
        internal abstract void AddPositionToList(TraversalPositionImpl position);
        /// <summary>
        /// Returns the next position from the list.
        /// </summary>
        /// <returns></returns>
        internal abstract TraversalPositionImpl GetNextPositionFromList();
        /// <summary>
        /// Returns <CODE>true</CODE> if there are no more nodes to traverse in the
        /// list, <CODE>false</CODE> otherwise.
        /// </summary>
        /// <returns></returns>
        internal abstract bool ListIsEmpty();
        /// <summary>
        /// Returns <CODE>true</CODE> if the traverser subtype wants children
        /// processed in natural order, <CODE>false</CODE> if it prefers them
        /// processed in reverse order. See implementation comments in 
        /// <CODE>traverseToNextNode()</CODE> for more information.
        /// </summary>
        /// <returns></returns>
        internal abstract bool TraverseChildrenInNaturalOrder();

        #endregion

        #region Protected Implementations


        #endregion

        #region Public Implementations

        public virtual IEnumerator<Node> iterator()
        {
            return this;
        }
        /// <summary>
        /// 
        /// </summary>
        /// <returns></returns>
        public virtual bool HasNext()
        {
            // If we have one cached, then we're definitely go
            if (this.cachedNode != null)
            {
                return true;
            }
            // If not, check if we can find one
            else
            {
                this.cachedNode = this.TraverseToNextNode();
                return this.cachedNode != null;
            }
        }
        /// <summary>
        /// 
        /// </summary>
        /// <returns></returns>
        public virtual Node Next()
        {
            return this.NextNode();
        }
        /// <summary>
        /// 
        /// </summary>
        /// <returns></returns>
        public virtual Node NextNode()
        {
            Node nodeToReturn = this.cachedNode;

            // If no node is cached, then traverse to next
            if (nodeToReturn == null)
            {
                nodeToReturn = this.TraverseToNextNode();
            }

            // If we couldn't find a node by traversing, report this by
            // throwing a NoSuchElementException (as per java.util.IEnumerator )
            if (nodeToReturn == null)
            {
                throw new NoSuchElementException();
            }

            // Clear the cache
            this.cachedNode = null;

            return nodeToReturn;
        }
        /// <summary>
        /// 
        /// </summary>
        /// <returns></returns>
        public virtual List<Node> GetAllNodes()
        {
            // Temp storage
            List<Node> tempList = new List<Node>();

            // Traverse until the end, my beautiful friend
            while (this.MoveNext())
            {
                tempList.Add(this.NextNode());
            }

            // Return nodes
            return tempList;
        }
        /// <summary>
        /// Doc: does it create a new IEnumerator  or reuse the existing one? This is
        /// very important! It must be re-use, how else would currentPosition()
        /// make sense?
        /// </summary>
        /// <returns></returns>
        public IEnumerable<Node> Iterator()
        {
            throw new NotImplementedException();
        }
        /// <summary>
        /// 
        /// </summary>
        public virtual void Remove()
        {
            throw new UnsupportedOperationException();
        }
        /// <summary>
        /// 
        /// </summary>
        /// <param name="nsi"></param>
        /// <returns></returns>
        public virtual Traverser Sort(NodeSortInfo<Node> nsi)
        {
            List<Node> tempList = new List<Node>();

            // Traverse and get all remaining nodes
            while (this.MoveNext())
            {
                tempList.Add(this.NextNode());
            }

            //Collections.sort(tempList, nsi);
            return new SortedTraverser(tempList);
        }
        /// <summary>
        /// 
        /// </summary>
        /// <returns></returns>
        public virtual TraversalPosition CurrentPosition()
        {
            return traversalPosition;
        }

        #endregion

        #region Other Implementations

        #region Implementation of IEnumerable

        /// <summary>
        /// Returns an enumerator that iterates through the collection.
        /// </summary>
        /// <returns>
        /// A <see cref="T:System.Collections.Generic.IEnumerator`1"/> that can be used to iterate through the collection.
        /// </returns>
        /// <filterpriority>1</filterpriority>
        public IEnumerator<Node> GetEnumerator()
        {
            throw new NotImplementedException();
        }
        /// <summary>
        /// Returns an enumerator that iterates through a collection.
        /// </summary>
        /// <returns>
        /// An <see cref="T:System.Collections.IEnumerator"/> object that can be used to iterate through the collection.
        /// </returns>
        /// <filterpriority>2</filterpriority>
        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        #endregion

        #region Implementation of IDisposable

        /// <summary>
        /// Performs application-defined tasks associated with freeing, releasing, or resetting unmanaged resources.
        /// </summary>
        /// <filterpriority>2</filterpriority>
        public void Dispose()
        {
            throw new NotImplementedException();
        }

        #endregion

        #region Implementation of IEnumerator

        /// <summary>
        /// Advances the enumerator to the next element of the collection.
        /// </summary>
        /// <returns>
        /// true if the enumerator was successfully advanced to the next element; false if the enumerator has passed the end of the collection.
        /// </returns>
        /// <exception cref="T:System.InvalidOperationException">The collection was modified after the enumerator was created. 
        ///                 </exception><filterpriority>2</filterpriority>
        public bool MoveNext()
        {
            throw new NotImplementedException();
        }
        /// <summary>
        /// Sets the enumerator to its initial position, which is before the first element in the collection.
        /// </summary>
        /// <exception cref="T:System.InvalidOperationException">The collection was modified after the enumerator was created. 
        ///                 </exception><filterpriority>2</filterpriority>
        public void Reset()
        {
            throw new NotImplementedException();
        }
        /// <summary>
        /// Gets the element in the collection at the current position of the enumerator.
        /// </summary>
        /// <returns>
        /// The element in the collection at the current position of the enumerator.
        /// </returns>
        public Node Current
        {
            get { throw new NotImplementedException(); }
        }
        /// <summary>
        /// Gets the current element in the collection.
        /// </summary>
        /// <returns>
        /// The current element in the collection.
        /// </returns>
        /// <exception cref="T:System.InvalidOperationException">The enumerator is positioned before the first element of the collection or after the last element.
        ///                 </exception><filterpriority>2</filterpriority>
        object IEnumerator.Current
        {
            get { return Current; }
        }

        #endregion

        #endregion

        #endregion
    }
}